package com.jinan.algorithm.binarySearch;

public class SqrtCalculator {
    public static void main(String[] args) {
        int x = 24;
        System.out.println("Square root of " + x + " is " + binarySearch(x));
        System.out.println("Square root of " + x + " is " + NewtonSqrt(x));
    }

    //    二分查找
    public static int binarySearch(int x) {
        if (x == 0 || x == 1) {
            return x;
        }

        int l = 1, r = x, root = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                root = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return root;
    }

    //    牛顿迭代法
    public static int NewtonSqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        double c = x;
        double x0 = x / 2.0, x1 = (x0 + c / x0) / 2.0;
        while (Math.abs(x0 - x1) > 1e-10) {
            x0 = x1;
            x1 = (x0 + c / x0) / 2;
        }
        return (int) x1;
    }
}
